//颜色分类（颜色划分）
//https://leetcode.cn/problems/sort-colors/description/
public class Test {
    public static void main(String[] args) {
        //
    }
}

//老师建议：
//回顾一下之前写过的：移动零
//https://leetcode.cn/problems/move-zeroes/
class Solution1 {// 原先写过的
    public void moveZeroes(int[] nums) {
        //[0,dest]区间，已经处理过的、非零元素
        //[dest+1,cur-1]区间，已经处理过的、0元素
        //[cur,n-1]区间，未被处理的区间
        int dest = -1;
        int cur = 0;
        while (cur < nums.length) {
            if(nums[cur] != 0){
                dest++;
                int tmp = nums[cur];
                nums[cur] = nums[dest];
                nums[dest] = tmp;
//                nums[++dest] = nums[cur];
//                nums[cur] = 0;//若整个数组都没有0，这样写会导致0覆盖
            }
            cur++;
        }

    }
}

//用上边提到的“移动零”的写法，写一下快排


//本题代码：
class Solution {
    public void sortColors(int[] nums) {
        //区间划分
        //[0,left]——0
        //[left+1,i-1]——1
        //[i,right-1]——未扫描
        //[right,n-1]——2
        int left = -1, right = nums.length;
        int i = 0;
        while (i < right) {//注意这里的循环条件——right,而不是length-1
            if(nums[i] == 0){
                left++;
                int tmp = nums[left];
                nums[left] = nums[i];
                nums[i] = tmp;
                i++;
            }else if(nums[i] == 1){
                i++;
            }else{
                int tmp = nums[--right];
                nums[right] = nums[i];
                nums[i] = tmp;
                //注意：这里i不能++
            }
        }

    }
}
//老师的写法更简单明了
class SolutionPro {//25.3.12
    //多处涉及到元素交换，干脆封装一个方法
    public void swap(int[] nums, int i, int j) {
        int temp = nums[i];
        nums[i] = nums[j];
        nums[j] = temp;
    }
    public void sortColors(int[] nums) {
        int left = -1, right = nums.length,i = 0;
        while (i < right) {
            if(nums[i] == 0) swap(nums, i++,++left);
            else if(nums[i] == 1) i++;
            else swap(nums,--right,i);//这几个分支语句，都需要注意，是先++/--，还是先使用
        }

    }
}
